﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    /*
     1139. 最大的以 1 为边界的正方形
    中等
    135
    相关企业
    给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

 

    示例 1：

    输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
    输出：9
    示例 2：

    输入：grid = [[1,1,0,0]]
    输出：1
 

    提示：

    1 <= grid.length <= 100
    1 <= grid[0].length <= 100
    grid[i][j] 为 0 或 1
     */
    public class Solution1139
    {
        public int LargestBorderedSquare(int[][] grid)
        {
            //
            // 确定最大可能的边界长度
            var maxBorderLength= Math.Min(grid.Length, grid[0].Length);
            for(var borderLength=maxBorderLength;borderLength>=1;borderLength--)
            {
                //
                // 在可能的左上坐标取值范围内检查是否存在该边界长度的正方形
                for(int i=0; i < grid.Length; i++)
                {
                    for(int j = 0; j < grid[i].Length; j++)
                    {
                        if (IsSquare(grid, grid.Length, grid[i].Length,i,j,borderLength))
                        {
                            return borderLength*borderLength;
                        }
                    }                  
                }                
            }
            return 0;
        }
        /// <summary>
        /// 判断是否是一个长度为borderLength的正方形
        /// </summary>
        /// <param name="grid"></param>
        /// <param name="x"></param>
        /// <param name="y"></param>
        /// <param name="borderLength"></param>
        /// <returns></returns>
        private bool IsSquare(int[][] grid,int xLength,int yLength,int x,int y,int borderLength) 
        {
            if (borderLength <= xLength - x && borderLength <= yLength - y)
            {
                var result = true;
                //
                // 判断四条边界是否存在0
                {
                    var j = y;
                    for (int i = x; i < x + borderLength; i++)
                    {
                        if (grid[i][j] == 0) return false;
                    }
                }
                {
                    var i=x+borderLength-1;
                    for(int j = y; j < y + borderLength; j++)
                    {
                        if (grid[i][j] == 0) return false;
                    }
                }
                {
                    var j=y+borderLength-1;
                    for(int i = x; i < x + borderLength; i++)
                    {
                        if (grid[i][j] == 0) return false;
                    }
                }
                {
                    var i = x;
                    for(int j = y; j < y + borderLength; j++)
                    {
                        if (grid[i][j] == 0) return false;
                    }
                }
                return result;
            }
            else
            {
                return false;
            }
        }
        
    }
}
